<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3426：Poi2013 Tower Defense Game</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Poi2013 Tower Defense Game</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Poi2013 Tower Defense Game</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                Poi2013 Tower Defense Game                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p class="MsoNormal" align="left" style="margin-bottom: 10.75pt; background-color: white; background-position: initial initial; background-repeat: initial initial; "></p>
<div>&nbsp; Bytie is playing the computer game Tower Defense. His aim is to construct guard towers, so that they protect all of his domain. There are multiple towns in Bytie's domain, some of which are linked by bidirectional roads. If Bytie erects a guard tower in a city, then the tower protects its city and all the cities directly linked with it by roads.</div>
<div>&nbsp; Just as Bytie was pondering over the placement of guard towers in his domain, his elder sister Bytea entered the room. She glanced at the map displayed on the screen, and after a moment exclaimed: &quot;Oi, what is there to think about, clearly K &nbsp;towers suffice!&quot;.</div>
<div>&nbsp; Angered by his sister spoiling the fun, Bytie showed his sister the door, and began wondering what to do next. Pride will not let him construct more than K &nbsp;towers. He has an up his sleeve though: he can research a technology that will allow him to constructimproved guard towers. An improved guard tower protects not only the town it was erected in and its immediate neighbors but also the towns that are further away. Formally, an improved guard tower built in the town U protects the town V &nbsp;if either of the following holds:</div>
<div>U=V;</div>
<div>there is a direct road from U to V ;</div>
<div>or there is such a town W that there are direct roads from U to W and from W to V.</div>
<div>Of course, Bytie still strives to erect at most K towers, but he has no qualms about making these the improved guard towers.</div>
<div>有一天XYW在4399上玩一个塔防游戏：</div>
<div>请你给他一种用k座以内加强过的塔保护所有城市的方案</div>
<div>有n座城市由m条双向道路连接。XYW可以在城市中建防御塔，每一座防御塔可以保护它所在的城市以及和这座城市有道路直接连接的城市。</div>
<div>由于XYW比较蠢萌，他建了n座塔保卫了所有城市。</div>
<div>突然XYW的男人看到了他的电脑屏幕：我只要用k座塔就可以了。（保证存在仅用k座塔就可以保卫所有城市的情况）</div>
<div>XYW不想被他的男人嘲笑，于是他就开始想如何用k座塔保护所有城市。</div>
<div>由于XYW比较蠢萌，他想不出来。</div>
<div>于是他更改了游戏规则：每一座塔可以保护和它所在城市最短距离在两条道路以内的所有城市。</div>
<div></div>
<p class="MsoNormal" align="left" style="margin-bottom: 10.75pt; background-color: white; background-position: initial initial; background-repeat: initial initial; "></p>
<p></p></p><hr/><h3>输入格式</h3><p><div></div>
<div>
<p class="MsoNormal" align="left" style="background-color: white; margin-bottom: 10.75pt; "></p>
<p class="MsoNormal" align="left" style="margin-bottom: 10.75pt;">&nbsp; The towns in Bytie's domain are numbered from 1 to N. Next, M lines describing the roads follow. Each of those lines holds two integers, Ai and Bi (1&lt;=Ai,Bi&lt;=N,Ai&lt;&gt;Bi) , indicating that the towns no. Ai and Bi are directly linked by a bidirectional road. Each pair of towns is linked by at most a single road.</p>
<p class="MsoNormal" align="left" style="background-color: white; margin-bottom: 10.75pt; "></p>
</div>
<div>
<p></p>
</div></p><hr/><h3>输出格式</h3><p><div></div>
<div>
<p class="MsoNormal" align="left" style="background-color: white; margin-bottom: 10.75pt; "></p>
<p class="MsoNormal" align="left" style="margin-bottom: 10.75pt;">&nbsp; If more than one solution exists, any solution can be printed. Let us remind that any placement of no more than K improved towers will do - you need not minimize their number. You may assume that Bytea was correct, i.e., that the whole domain of Bytie can indeed be protected by K plain (not improved) guard towers. Thus a solution always exists.</p>
<p class="MsoNormal" align="left" style="background-color: white; margin-bottom: 10.75pt; "></p>
</div>
<p></p></p><hr/><h3>样例输入</h3><pre>9 8 3
1 2
2 3
3 4
1 4
3 5
4 6
7 8
8 9



</pre><hr/><h3>样例输出</h3><pre>3
1 5 7 
</pre><hr/><h3>提示</h3><p><p><a id="fck_paste_padding">﻿</a><span style="font-family: arial, verdana, helvetica, sans-serif;">2&lt;=n&lt;=500000,0&lt;=m&lt;=1000000</span></p></p><hr/><h3>题目来源</h3><p>鸣谢Jiry_2</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3426" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3426" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>